The present invention relates to Tenant Placement in Multitenant Databases for Profit Maximization.
With the increasing popularity of cloud computing, the benefits of hosting applications on a cloud service provider (including IaaS, PaaS and SaaS) becomes more and more apparent and widely accepted. It not only avoids high capital expenditure, but also minimizes the risk of under-provisioning and over-provisioning using an elastic, pay-as-you-go type approach. From the cloud service provider's perspective, to achieve economies of scale, an important practice is to use each physical server to host multiple tenants (a.k.a. multitenancy). One approach is to use virtual machines with fixed resources such as Amazon EC2 instances. It provides good isolations among different tenants, but the downside is the compromise of resource sharing. Another possibility is that all tenants use the same resource pool, so that occasional workload bursts from a few tenants can be gracefully handled. Such a model is often used in Software as a Service platforms where tenants run Web-based services that are accessed by Web users. Usually the revenue of a cloud service provider is generated by meeting the service level agreements (SLA) the provider negotiates with each tenant, in terms of various criteria such as response time, availability, throughput, among others. For example, a service level agreement may be that if the response time of the query is less than 5 seconds, the tenant pays the provider for the service, otherwise the provider pays the tenant a penalty. Since maximizing the profit is the ultimate goal of a cloud service provider, it should be the main optimization criterion of decision-making in multitenant databases.
There has been a great interest in exploiting the cloud as a platform for database as a service. As with other cloud-based services, database services may enjoy cost efficiency through consolidation: hosting multiple databases within a single physical server. Aggressive consolidation, however, may hurt the service quality, leading to SLA violation penalty, which in turn reduces the total business profit, or SLA profit.
Cloud service providers have conflicting goals when distributing the tenants on computing servers. On the one hand, purchasing, renting or using each server incurs an expense, and thus the provider is motivated to use as few servers as possible. On the other hand, if a server hosts too many tenants and is too crowded, it may lead to a high chance of violating the service level agreements, which incurs penalties. Thus the tenant placement should be carefully planned in order to minimize the total cost.
One may naturally think of the connection between tenant placement and bin packing, a classic NP-hard problem. It is worthwhile to point out that tenant placement has several additional complications compared with bin packing First, in bin packing (as well as its variations studied so far, to the knowledge), each item has a fixed size, whereas each cloud tenant's size may vary with time (e.g., a tenant may have more users on weekdays than on weekends). Second, in bin packing, a hard constraint is that the total size of all items in a bin cannot exceed the bin's capacity. In tenant placement there is no such constraint, but the more tenants a server hosts, the more SLA violations may occur. Lastly, the optimization goal of bin packing is minimizing the total number of bins, whereas in tenant placement the goal is to minimize the total cost, which includes the cost of the servers and the penalty of SLA violations.
In cloud computing, there is an opportunity for workload consolidation for better resource utilization. We consider the case of database consolidation, which is often called multitenant databases. While consolidation helps to reduce operational cost, too aggressive consolidation may increase SLA violation penalty due to the crowded environment, which leads to the reduced total profit. Hence the problem is: given a set of tenants, their workload information (query arrival rate, query execution time), their service level agreement (SLA) functions and the cost of operating a server, how many servers should we use and how to assign tenants to the servers so that the total cost (server cost plus SLA penalty cost) is minimized.
Conventional systems are not profit-driven and do not aim at minimizing SLA violation penalties. Their optimization goal is usually minimizing the number of servers subject to certain constraints (such as no server may be overload, or a certain throughput needs to be achieved), and they usually make restrictive assumptions such as the load of each tenant is fixed, there are a certain number of types of tenants, among others.